package com.hspedu.newData.dmsxl.树.构造二叉树;

import com.hspedu.newData.dmsxl.ds.ListNode;
import com.hspedu.newData.dmsxl.ds.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-13 
 * @Version: 1.0
 */

// 优化？
// 使用快慢指针直接获得链表的中间节点
public class LC109有序链表转换为二叉搜索树 {

    public TreeNode sortedListToBST(ListNode head) {

        List<Integer> list = new ArrayList<>();
        while (head!=null){
            list.add(head.val);
            head = head.next;
        }
        TreeNode treeNode = find(list, 0, list.size());

        return treeNode;
    }


    public TreeNode find(List<Integer> list,int begin,int end){
        if (begin >= end){
            return null;
        }

        int mid = begin + (end - begin) /2;
        TreeNode root = new TreeNode(list.get(mid));

        root.left = find(list,begin,mid);
        root.right = find(list,mid+1,end);

        return root;
    }
}
